package com.lw.leetcode.tree.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1649. 通过指令创建有序数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/9 17:08
 */
public class CreateSortedArray {

    public static void main(String[] args) {
        CreateSortedArray test = new CreateSortedArray();

        // 0
        int[] arr = {1, 1};

        // 4
//        int[] arr = {1, 3, 3, 3, 2, 4, 2, 1, 2};

        // 4
//        int[] arr = Utils.getArr(100000, 1, 100000);

        int sortedArray = test.createSortedArray(arr);
        System.out.println(sortedArray);
    }

    public int createSortedArray(int[] instructions) {
        int length = instructions.length;
        if (length < 3) {
            return 0;
        }
        Node root = new Node(1, 100000);
        long sum = 0;
        Map<Integer, Integer> map = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            int v = instructions[i];
            int c = map.getOrDefault(v, 0);
            int n = find(root, v);
            sum = (sum + Math.min(i - n, n - c)) % 1000000007;
            map.put(v, c + 1);
            add(root, v);
        }
        return (int) sum;
    }

    private int find(Node node, long val) {
        if (node == null) {
            return 0;
        }
        long st = node.st;
        long end = node.end;
        if (st == end || end <= val) {
            return node.count;
        }
        long m = st + ((end - st) >> 1);
        if (val <= m) {
            return find(node.left, val);
        } else {
            return (node.left == null ? 0 : node.left.count) + find(node.right, val);
        }
    }

    private void add(Node node, long val) {
        long st = node.st;
        long end = node.end;
        node.count++;
        if (st == end) {
            return;
        }
        long m = st + ((end - st) >> 1);
        if (val <= m) {
            if (node.left == null) {
                node.left = new Node(st, m);
            }
            add(node.left, val);
        } else {
            if (node.right == null) {
                node.right = new Node(m + 1, end);
            }
            add(node.right, val);
        }
    }

    private static class Node {
        private long st;
        private long end;
        private int count;
        private Node left;
        private Node right;
        private Node(long st, long end) {
            this.st = st;
            this.end = end;
        }
    }

}
